#pragma cone
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;

void GetNext(const string& sub, vector<int>& next)
{
    assert(sub.size()!=0||next.size()!=0);

    next[0]=-1;
    next[1]=0;
    int i=2;
    int k=0;

    int lensub=sub.size();
    while(i<lensub)
    {
        if(k==-1||sub[i-1]==sub[k])
        {
            next[i]=k+1;
            i++,k++;
        }else
        {
            k=next[k];
        }
    }
}
int KMP(const string& str,const string& sub,const int pos)
{
    if(str.size()==0 || sub.size()==0) return -1;
    assert(pos>=0||pos<str.size());//传入非法值

    int lenstr=str.size();
    int lensub=sub.size();
    int i=pos;
    int j=0;

    vector<int> next(lensub);//sub的
    GetNext(sub,next);

    while(i<lenstr&&j<lensub)
    {
        //j== -1 在next数组str[i]!=sub[j]
        if(j==-1||str[i]==sub[j])
        {
            i++,j++;
        }else 
        {
            j=next[j];
        }
    }
    if(j>=lensub)
        return i-j;
    
    return -1;//没有找到
}

int main()
{
    cout<<(KMP("ababcabcdabcde","abcd",0))<<endl;
    cout<<(KMP("ababcabcdabcde","abcdf",0))<<endl;
    cout<<(KMP("ababcabcdabcde","ab",0))<<endl;
    return 0;
}